<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>
    // 封装链表类
    function LinkedList () {
      // 内部的类: 节点类
      function Node (data) {
        this.data = data
        this.next = null
      }

      // 属性
      this.head = null
      this.length = 0

      // 1. 追加 方法
      LinkedList.prototype.append = function (data) {
        // 创建新的节点
        var newNode = new Node(data)

        if (this.length == 0) { // 是第一个节点
          this.head = newNode
        } else { // 不是第一个节点
          // 找到最后一个节点
          var current = this.head
          while (current.next) {
            current = current.next
          }

          // 最后节点的next指向新的节点
          current.next = newNode
        }
        
        // length + 1
        this.length += 1
      }

      // 2. toString方法
      LinkedList.prototype.toString = function () {
        // 定义变量
        var current = this.head
        var listString = ''

        // 循环获取一个个的节点
        while (current) {
          listString += current.data + ' '
          current = current.next
        }
        return listString
      }

      // 3. insert方法
      LinkedList.prototype.insert = function (position, data) {
        // 对position进行越界判断
        if (position < 0 || position > this.length)  return false
        
        // 根据data创建newNode
        var newNode = new Node(data)

        // 判断插入的位置是否是第一个
        if (position == 0) {
          newNode.next = this.head
          this.head = newNode
        } else {
          var index = 0
          var current = this.head
          var previous = null
          while (index++ < position) {
            previous = current
            current = current.next
          }

          newNode.next = current
          previous.next = newNode
        }

        // length + 1
        this.length += 1
        return true
      }

      // 4. get方法
      LinkedList.prototype.get = function (position) {
        // 越界判断
        if (position < 0 || position >= this.length) return null

        // 获取对应的data
        var current = this.head
        var index = 0
        while (index++ < position) {
          current = current.next
        }

        return current.data
      }

      // 5. indexOf方法
      LinkedList.prototype.indexOf = function (data) {
        // 定义变量
        var current = this.head
        var index = 0

        // 开始查找
        while (current) {
          if (current.data == data) {
            return index
          }
          current = current.next
          index +=1
        }

        // 找到最后没找到 返回-1
        return -1
      }

      // 6. update方法
      LinkedList.prototype.update = function (position, newData) {
        // 越界判断
        if (position < 0 || position >= this.length) return false

        // 查找正确的节点
        var current = this.head
        var index = 0
        while (index++ < position) {
          current = current.next
        }

        // 将position位置的node的data修改成newData
        current.data = newData

        return true
      }

      // 7. removeAt方法
      LinkedList.prototype.removeAt = function (position) {
        // 越界判断
        if (position < 0 || position >= this.length) return false

        // 判断是否删除的是第一个节点
        var current = this.head
        if (position == 0) {
          this.head = this.head.next
        } else {
          var index = 0
          var previous = null
          while (index++ < position) {
            previous = current
            current = current.next
          }

          // 前一个节点的next指向current的next即可
          previous.next = current.next
        }

        this.length -= 1
        return current.data
      }

      // 8. remove方法
      LinkedList.prototype.remove = function (data) {
        // 获取data在列表中的位置
        var position = this.indexOf(data)

        // 根据位置信息 删除节点
        return this.removeAt(position)
      }

      // 9. isEmpty方法
      LinkedList.prototype.isEmpty = function () {
        return this.length == 0
      }
      // 10. size方法
      LinkedList.prototype.size = function () {
        return this.length
      }
    }

    // 测试代码
    // 1. 创建LinkedList
    var list = new LinkedList()

    // 2. 测试append方法
    list.append('a')    
    list.append('b')    
    list.append('c')
    alert(list)

    // 3. 测试insert方法 a b c
    // list.insert(1,'1') // a 1 b c
    // list.insert(3,'2') // a 1 b 2 c
    // list.insert(5,'3') // a 1 b 2 c 3
    // alert(list)

    // 4. 测试get方法
    // alert(list.get(0))

    // 5. 测试indexOf方法
    // alert(list.indexOf('c'))

    // 6. 测试update方法
    // list.update(0, '1')
    // list.update(1, '2')
    // list.update(2, '3')
    // alert(list)

    // 7. 测试removeAt方法
    // list.removeAt(2)
    // alert(list)

    // 8. 测试remove方法
    // list.remove('b')
    // alert(list)

    // 9. 测试isEmpty size方法
    // alert(list.isEmpty())
    // alert(list.size())
  </script>
</body>
</html>